Applications are programs that perform tasks on a computer. Applications save objects on a computer to cache for many reasons. Applications usually save objects to cache on a storage device so that the application can quickly access the object at a subsequent time. Objects placed in cache by an application may be used over and over again, or their use may be temporary in nature. An example of an object placed in cache that would be used over and over again is an object file containing login information for an e-mail reader. An example of an object placed in cache that would be temporary in nature is an image appearing on a rarely accessed Web page, or appearing in a rarely accessed streaming video broadcast. In the case of a rarely accessed Web page, or a streaming video broadcast, once the temporary cached object has been viewed, the viewer moves on to something else, and may never view that object again. Both objects cached for ongoing use and objects cached for temporary use take up volatile memory and persistent storage space. By taking up volatile memory and persistent storage space, the cached objects degrade the overall performance of the computer system. Various programs, algorithms, or routines (hereafter programs) exist to improve computer system performance by automatically removing unneeded files from the cache.
Persons skilled in the art refer to programs that automatically remove unneeded files from a cache as eviction programs. Other names for eviction programs are cache cleaning programs and garbage collection programs. As used herein, the term eviction program shall mean any program, algorithm, or routine that automatically removes objects from a cache in which the objects are stores. The simplest eviction program deletes the oldest object from the cache when more room is required in the cache. More elaborate eviction programs identify and delete unnecessary objects, while retaining useful objects in the cache. The more elaborate eviction programs fall into two categories: I/O feedback eviction programs and database tracking eviction programs.
I/O Feedback eviction programs monitor input/output (I/O) operations during the eviction of one object and use feedback from the evicted object to identify candidate objects to be evicted later. U.S. Pat. No. 6,718,438 is one example of a feedback eviction program that uses feedback from evicted candidates to identify new candidates. Another form of I/O feedback eviction programs reorganizes the cache whenever an object is fetched or updated to allow for faster access to objects identified for eviction. Reorganizing the cache may involve moving a cached object from one storage medium to another storage medium. U.S. Pat. No. 6,480,939 discloses a method of filtering fetches to enhance eviction of cached objects. I/O feedback eviction programs consume both computer hardware and software resources to identify and evict objects from cache.
Database tracking eviction programs, that use a database to track and delete objects in a cache, have an advantage over feedback eviction programs because fewer hardware resources are required to maintain the cache. The database tracking eviction program catalogs metadata related to the objects in the cache, and reorganizes and reprioritizes the list of objects in the cache without reorganizing the cached objects themselves on the storage device.
Database tracking eviction programs use attributes from the object's metadata to identify eviction candidates. A commonly used attribute for determining eviction candidates is the age of the object. Other attributes in the object's metadata that can be used in eviction determinations include the creator of the object, the time of last use, or the object type. Attributes in the object's metadata can indicate that the object is useful and should not be deleted. Although database tracking eviction programs do not require I/O hardware overhead of the I/O feedback eviction programs, the database tracking eviction programs consume extensive memory resources as the size of the cache grows. The memory use of the database tracking eviction program ultimately degrades the performance of the computer system. Therefore, a need exists for a method to reduce the memory requirements of database tracking eviction programs.